package com.lw.leetcode.linked.c;

import com.lw.test.util.Utils;

import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * 1340. 跳跃游戏 V
 *
 * @author liw
 * @version 1.0
 * @date 2022/11/15 15:36
 */
public class MaxJumps {

    public static void main(String[] args) {
        MaxJumps test = new MaxJumps();

        // 4
//        int[] arr = {6, 4, 14, 6, 8, 13, 9, 7, 10, 6, 12};
//        int d = 2;

        // 1
//        int[] arr = {3, 3, 3, 3, 3};
//        int d = 3;

        // 7
//        int[] arr = {7, 6, 5, 4, 3, 2, 1};
//        int d = 1;

        // 2
//        int[] arr = {7, 1, 7, 1, 7, 1};
//        int d = 2;

        // 1
//        int[] arr = {60};
//        int d = 1;


        // 10
//        int[] arr = {80, 94, 32, 12, 20, 39, 92, 41, 85, 45, 85, 84, 65, 53, 6, 37, 39, 52, 49, 84, 64, 57, 81, 38, 20, 45, 43, 23, 35, 78, 95, 29, 66, 22, 30, 23, 40, 37, 76, 66, 12, 84};
//        int[] arr = {79, 50, 41, 88, 35, 29, 69, 73, 59, 73, 84, 21, 43, 32, 25, 14, 5, 60, 48, 80, 86, 40, 30, 7, 80, 94, 32, 12, 20, 39, 92, 41, 85, 45, 85, 84, 65, 53, 6, 37, 39, 52, 49, 84};
//        int d = 8;


        // 13
//        int[] arr = {70,93,10,67,77,24,62,39,61,98,84,86,6,23,73,68,52,31,73,47,73,50,37,80,6,63,30,16,58,90,56,86,7,56,91,53,62,24,85,7,79,56,31,66,12,52,62,67,22,3,98,100,12,40,38,13,54,56,74,98,54,76,12,71,95,69,13,45,25,96,41,29,29,7,100,86,44,13,37,24,4,75,38,35,30,22,79,6,27,9,52,49,87,9,99,46,11,9,83,2,17,98,81,48,42,7,23,65,98,41,45,84,7,3,93,29,51,76,55,93,13,30,98,62,35,51,44,86,58,57,71,46,73,33,22,59,1,74,34,44,82,26,37,74,61,48,90,86,28,27,1,45,69,58,87,35,9,67,16,94,100,67,78,49,94,90,74,16,63,33,59,19,67,72,99,31,79,97,34,49,51,30,49,38,72,6,82,99,79,21,29,80,37,90,74,28,48,74,89,72,27,57,96,79,80,88,47,72,66,7,26,16,33,73,72,21,91,50,62,43,3,47,94,67,87,8,85,93,54,41,72,47,94,11,63,9,90,8,90,61,86,41,78,41,95,31,46,11,99,24,16,56,76,70,20,50,63,15,80};
//        int[] arr = {79, 50, 41, 88, 35, 29, 69, 73, 59, 73, 84, 21, 43, 32, 25, 14, 5, 60, 48, 80, 86, 40, 30, 7, 80, 94, 32, 12, 20, 39, 92, 41, 85, 45, 85, 84, 65, 53, 6, 37, 39, 52, 49, 84};
//        int d = 259;


        //
        int[] arr = Utils.getArr(1000, 1, 1);
        int d = 1000;
        System.out.println(d);

        int i = test.maxJumps(arr, d);
        System.out.println(i);
    }

    public int maxJumps(int[] arr, int d) {
        Node st = new Node(Integer.MAX_VALUE, -1);
        Node end = new Node(Integer.MAX_VALUE, -1);
        Node item = st;
        int length = arr.length;
        for (int i = 0; i < length; i++) {
            Node node = new Node(arr[i], i);
            node.pre = item;
            item.next = node;
            item = node;
        }
        item.next = end;
        end.pre = item;
        int max = 0;
        int count = length;
        Stack<Node> stack = new Stack<>();
        while (count > 0) {
            item = st.next;
            stack.clear();
            while (item != end) {
                Node pre = item.pre;
                Node next = item.next;
                int val = item.val;
                max = Math.max(max, item.step);
                if (val < pre.val && val < next.val) {
                    if (item.index - pre.index <= d) {
                        pre.step = Math.max(pre.step, item.step + 1);
                    }
                    if (next.index - item.index <= d) {
                        next.step = Math.max(next.step, item.step + 1);
                    }
                    count--;
                    pre.next = next;
                    next.pre = pre;
                } else if (val == pre.val && val < next.val) {
                    while (!stack.isEmpty()) {
                        Node peek = stack.peek();
                        if (peek.val <= val) {
                            stack.pop();
                        } else {
                            break;
                        }
                    }
                    if (!stack.isEmpty()) {
                        Node peek = stack.peek();
                        if (item.index - peek.index <= d) {
                            peek.step = Math.max(peek.step, item.step + 1);
                        }
                    }
                    if (next.index - item.index <= d) {
                        next.step = Math.max(next.step, item.step + 1);
                    }
                    count--;
                    pre.next = next;
                    next.pre = pre;
                } else {
                    while (!stack.isEmpty()) {
                        Node peek = stack.peek();
                        if (peek.val <= val) {
                            stack.pop();
                        } else {
                            break;
                        }
                    }
                    stack.add(item);
                }
                item = item.next;
            }
        }
        return max + 1;
    }

    public static class Node {
        private int val;
        private int index;
        private int step;
        private Node next;
        private Node pre;

        public Node(int val, int index) {
            this.val = val;
            this.index = index;
        }
    }

}
